package binarytree

// https://leetcode.cn/problems/count-complete-tree-nodes/

// calculates the number of nodes in a complete binary tree.
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := 0
	rightDepth := 0
	leftNode := root
	rightNode := root

	// 如下的计算中 leftDepth 和 rightDepth 都至少是1
	for leftNode != nil {
		leftDepth++
		leftNode = leftNode.Left
	}

	// 注意这里是一路向右，也就是二叉树的最右侧的分支，根据完全二叉树的性质，如果最右侧的高度和最左侧的高度相等，说明这颗树是满的
	for rightNode != nil {
		rightDepth++
		rightNode = rightNode.Right
	}

	// 特例：满二叉树，节点数量就是深度值 depth 的2的幂次方减1
	if leftDepth == rightDepth {
		return (1 << leftDepth) - 1 // 2^leftDepth - 1
	}

	// 不是满二叉树，就执行到此处
	// 此处的执行，意味着还要重复计算一遍深度
	// 但是因为满二叉树的特点，左子树和右子树总有一颗是满的，所以至少有一半是不需要重新计算的
	// 而对于需要重新计算的子树，递归到叶子结点其实也是一颗满二叉树，会走一次上边的特例
	return 1 + countNodes(root.Left) + countNodes(root.Right)
}

// CountCompleteBinaryTreeNodes
// 普通的二叉树用来计算节点数的函数
func CountNodesCommon(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + CountNodesCommon(root.Left) + CountNodesCommon(root.Right)
}

// 这两个方法的区别在于，`countNodes` 是专门针对完全二叉树的优化版本，利用了完全二叉树的性质来减少计算量，而 `CountNodesCommon` 则是通用的二叉树节点计数方法，适用于所有类型的二叉树。对于完全二叉树，`countNodes` 的性能更优，因为它避免了不必要的递归调用。

// 所有的左叶子节点之和
func SumLeftNodes(root *TreeNode) int {
	// 思路
	// 深度优先遍历即可
	// 自上而下，碰到方向是左边的就加上这个node的数即可
	if root == nil {
		return 0
	}

	sum := 0
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, direction int) {
		if node == nil {
			return
		}
		if direction == 1 && node.Left == nil && node.Right == nil {
			sum += node.Val
		}
		dfs(node.Left, 1)
		dfs(node.Right, 0)
	}
	dfs(root, 0)
	return sum
}
